module Entropy  where
import IO

-- Quick sort
sort :: Ord a => [a] -> [a]
sort [] = []
sort (a:as) = (sort [b | b<-as, b<=a]) ++ [a] ++ (sort [b | b<-as, b>a])

-- Util function: 
-- on input we have tuples with the same first element
-- on output is the single tuple with the second elements in the single array
joinGroup :: [(a,b)] -> (a,[b])
joinGroup ((a,b):t) = (a, b:(map snd t))

--
joinGroups :: [[(a,b)]] -> [(a,[b])]
joinGroups = map joinGroup

-- Splits input array into disjunctive subarrays
-- using the communicative predicate function
-- From "AAABBCCAAA" we get ["AAAAAA", "BB", "CCC"]
-- (order is not preserved)
group :: (a->a->Bool) -> [a] -> [[a]]
group f = g [] where
	g result [] = result
	g result (h:t) = g (newGroup:result) rest where
		newGroup = h:(filter (f h) t)
		rest = filter (not.f h) t

-- Splits input array into consequent subarrays using function:
-- From "AAABBCCAAA" we get ["AAA", "BB", "CCC", "AAA"] 
-- (order is not preserved)
groupNeighbs :: (a->a->Bool) -> [a] -> [[a]]
groupNeighbs f  = g [] []  where
	g result [] [] = result
	g result [] (a:as) = g result [a] as
	g result buf [] = buf : result
	g result buf (a:as)  = 
		if (f a $ head buf) then g result (a:buf) as 
			else g (buf:result) [a] as
		
-- Util function to group tuples by the first elem
same1st :: Eq a => (a,b) -> (a,c) -> Bool
same1st (a1,_) (a2,_) = a1 == a2

joinNeighbsBy1st :: Eq a => [(a,b)]->[(a,[b])]
joinNeighbsBy1st = joinGroups . groupNeighbs same1st

joinBy1st :: Eq a => [(a,b)]->[(a,[b])]
joinBy1st = joinGroups . group same1st

groupEntropy :: ([b]->Double) -> [(a,[b])] -> Double
groupEntropy f = entropy . probabilities f . map snd

-- Get probability of disjunctive event sequence 
-- by their relative measure
probabilities :: ([b]->Double) -> [[b]] -> [Double]
probabilities f arr = map (\x-> (f x)/total) arr where
	total = sum $ map f arr

-- Entropy of the event sequence by their probabilities
entropy :: [Double] -> Double
entropy arr = (sum $ map h arr)/(log 2) where h x = -x * (log x)

-- Various attempts to count the entropy


-- Plain entropy of the sequence
linesEntropy :: Eq a => ([b]->Double) -> [(a, b)] -> Double
linesEntropy f arr = entropy $ probabilities f $ map snd $ joinBy1st arr

ragsEntropy :: Eq a => ([b]->Double) -> [(a,b)] -> Double
ragsEntropy f = entropy . probabilities f . map snd .	joinNeighbsBy1st

actorsEntropy :: Eq a => ([b]->Double) -> [(a,b)] -> Double
actorsEntropy f arr = sum $ map (groupEntropy f) $ group same1st $ joinNeighbsBy1st arr

m :: [a] -> Double
m = fromIntegral . length 
